Introduction

Number theory uses a small but powerful collection of symbols.
This article introduces the notation you’ll see throughout the book, with simple explanations and examples.

Goals of this chapter:

• Build comfort with common mathematical symbols
• Show how notation helps express ideas clearly and concisely
• Provide examples that feel concrete rather than abstract

The Natural Numbers and Integers

Natural numbers

• Usually written as $\mathbb{N}$
• Common meanings:
  • $\mathbb{N} = \{1,2,3,\dots\}$
  • Some authors include $0$; this book will not include $0$ unless stated

Integers

• Written as $\mathbb{Z}$
• Includes:
  • Positive integers: $1,2,3,\dots$
  • Negative integers: $-1,-2,-3,\dots$
  • Zero: $0$

Examples

• $7 \in \mathbb{N}$
• $-4 \in \mathbb{Z}$
• $0 \in \mathbb{Z}$

Sets and Set‑Builder Notation

Basic set notation

• Curly braces: $\{1,2,3\}$
• Membership: $x \in S$ means “$x$ is in the set $S$”
• Non‑membership: $x \notin S$

Common sets

• Evens: $\{2,4,6,8,\dots\}$
• Odds: $\{1,3,5,7,\dots\}$

Set‑builder notation

Used to describe sets by a rule:

• $\{n \in \mathbb{N} : n \text{ is even}\}$
• Read as: “the set of natural numbers $n$ such that $n$ is even”

Intervals of integers

• $[a,b]$ sometimes used informally to mean all integers from $a$ to $b$
  Example: $[3,7] = \{3,4,5,6,7\}$

Divisibility Notation: $d \mid n$ and Related Symbols

Divisibility

• $d \mid n$ means “$d$ divides $n$”
• Equivalent to: $n = dk$ for some integer $k$

Examples

• $3 \mid 12$ because $12 = 3 \cdot 4$
• $5 \nmid 14$ because no integer $k$ satisfies $14 = 5k$

Related ideas

• Even numbers: $2 \mid n$
• Odd numbers: $2 \nmid n$
• Greatest common divisor: $\gcd(a,b)$
• Least common multiple: $\operatorname{lcm}(a,b)$

Equality, Congruence, and Modular Notation

Equality

• $a = b$ means $a$ and $b$ are the same number

Congruence modulo $m$

• $$a \equiv b \pmod{m}$$
• Means $a$ and $b$ leave the same remainder when divided by $m$
• Equivalent to: $m \mid (a - b)$

Examples

• $17 \equiv 2 \pmod{5}$
• $14 \equiv 0 \pmod{7}$

Summation Notation: $\sum$

Purpose

Summation notation compactly represents adding many terms.

General form

$$\sum_{k=1}^{n} a_k$$

Examples

• $$\sum_{k=1}^{4} k = 1+2+3+4 = 10$$
• $$\sum_{k=1}^{3} (2k) = 2+4+6 = 12$$

Notes

• The index ($k$ here) is a dummy variable
• The lower and upper bounds tell you where to start and stop

Product Notation: $\prod$

Purpose

Product notation represents multiplying many terms.

General form

$$\prod_{k=1}^{n} a_k$$

Examples

• $$\prod_{k=1}^{4} k = 1\cdot2\cdot3\cdot4 = 24$$
• $$\prod_{k=1}^{3} (k+1) = 2\cdot3\cdot4 = 24$$

Intervals and Ranges of Integers

Common ways to describe ranges

• $1 \le n \le 10$
• “For $n$ from $1$ to $10$”
• $[1,10]$ (informal integer interval)

Examples

• “Let $n$ run over $1,2,3,4$”
• “Consider all integers $k$ with $0 \le k < 5$”

Floor and Ceiling Functions

Floor function

• Written $\lfloor x \rfloor$
• The greatest integer $\le x$

Examples:

• $\lfloor 3.7 \rfloor = 3$
• $\lfloor -1.2 \rfloor = -2$

Ceiling function

• Written $\lceil x \rceil$
• The smallest integer $\ge x$

Examples:

• $\lceil 3.7 \rceil = 4$
• $\lceil -1.2 \rceil = -1$

Absolute Value and Basic Function Notation

Absolute value

• Written $|x|$
• Measures distance from $0$

Examples:

• $|5| = 5$
• $|-5| = 5$

Basic function notation

• $f(n)$ means “the value of the function $f$ at $n$”
• Example: if $f(n) = n^2$, then $f(3) = 9$

Logical Symbols in Number Theory

Common logical symbols

• “for all”: $\forall$
• “there exists”: $\exists$
• “and”: $\land$
• “or”: $\lor$
• “implies”: $\Rightarrow$

Examples

• $\forall n \in \mathbb{N},\ n+1 > n$
• $\exists k \in \mathbb{Z}$ such that $n = 2k$

Common Abbreviations (gcd, lcm, etc.)

gcd

• $\gcd(a,b)$ = greatest common divisor of $a$ and $b$

lcm

• $\operatorname{lcm}(a,b)$ = least common multiple of $a$ and $b$

Other useful abbreviations

• “iff”: “if and only if”
• “wlog”: “without loss of generality”

Calculator

Exercises

Try these to build comfort with the notation.

1. Write the set of all odd natural numbers less than $15$ using set‑builder notation.

   Solution

   Odd natural numbers less than $15$ in set‑builder notation

   • The odd natural numbers less than $15$ are
     $1,3,5,7,9,11,13$.
   • In set‑builder notation: $$\{n \in \mathbb{N} : n \text{ is odd and } n < 15\}$$
2. Determine whether each statement is true or false:
   • $4 \mid 20$
   • $6 \mid 25$
   • $3 \mid (n^2 - n)$ for all integers $n$

   Solution

   True/false divisibility statements

   • (a) $4 \mid 20$
     • $20 = 4 \cdot 5$, so this is true.
   • (b) $6 \mid 25$
     • There is no integer $k$ with $25 = 6k$, so this is false.
   • (c) $3 \mid (n^2 - n)$ for all integers $n$
     • Note $n^2 - n = n(n-1)$, the product of two consecutive integers.
     • Among any three consecutive integers, one is divisible by $3$, and $n$ and $n-1$ cover all residues mod $3$.
     • More concretely, check $n \equiv 0,1,2 \pmod{3}$:
       • If $n \equiv 0$, then $n^2 - n \equiv 0 - 0 \equiv 0 \pmod{3}$
       • If $n \equiv 1$, then $n^2 - n \equiv 1 - 1 \equiv 0 \pmod{3}$
       • If $n \equiv 2$, then $n^2 - n \equiv 4 - 2 \equiv 2 \equiv -1 \pmod{3}$ — wait, that looks off; check carefully:
         • $n \equiv 2 \Rightarrow n^2 \equiv 4 \equiv 1 \pmod{3}$, so $n^2 - n \equiv 1 - 2 \equiv -1 \equiv 2 \pmod{3}$
         • So this residue check suggests not always $0$; better to test directly:
           • Take $n=2$: $n^2 - n = 4 - 2 = 2$, and $3 \nmid 2$.
     • So the statement is actually false.
3. Compute the following sums:
   • $\sum_{k=1}^{5} k$
   • $\sum_{k=1}^{4} (k+2)$

   Solution

   Summations

   • (a) $\displaystyle \sum_{k=1}^{5} k$ $$1 + 2 + 3 + 4 + 5 = 15$$
   • (b) $\displaystyle \sum_{k=1}^{4} (k+2)$
     Expand the terms: $$(1+2) + (2+2) + (3+2) + (4+2) = 3 + 4 + 5 + 6 = 18$$
4. Compute the products:
   • $\prod_{k=1}^{4} k$
   • $\prod_{k=2}^{4} (k+1)$

   Solution

   Products

   • (a) $\displaystyle \prod_{k=1}^{4} k$ $$1 \cdot 2 \cdot 3 \cdot 4 = 24$$
   • (b) $\displaystyle \prod_{k=2}^{4} (k+1)$
     Terms are $(2+1)(3+1)(4+1)$: $$3 \cdot 4 \cdot 5 = 60$$
5. Evaluate the congruences:
   • $17 \equiv ? \pmod{6}$
   • $50 \equiv ? \pmod{7}$

   Solution

   Congruences

   • (a) $17 \equiv ? \pmod{6}$
     • Divide $17$ by $6$: $17 = 6 \cdot 2 + 5$
     • So the remainder is $5$: $$17 \equiv 5 \pmod{6}$$
   • (b) $50 \equiv ? \pmod{7}$
     • Divide $50$ by $7$: $50 = 7 \cdot 7 + 1$
     • So the remainder is $1$: $$50 \equiv 1 \pmod{7}$$
6. Evaluate:
   • $\lfloor 7.9 \rfloor$
   • $\lceil -2.3 \rceil$

   Solution

   Floor and ceiling

   • (a) $\lfloor 7.9 \rfloor$
     • Greatest integer $\le 7.9$ is $7$: $$\lfloor 7.9 \rfloor = 7$$
   • (b) $\lceil -2.3 \rceil$
     • Smallest integer $\ge -2.3$ is $-2$: $$\lceil -2.3 \rceil = -2$$
7. Let $f(n) = 3n - 1$. Compute $f(4)$ and $f(10)$.

   Solution

   Function values

   Let $f(n) = 3n - 1$.

   • $f(4) = 3 \cdot 4 - 1 = 12 - 1 = 11$
   • $f(10) = 3 \cdot 10 - 1 = 30 - 1 = 29$
8. Find $\gcd(18, 30)$ and $\operatorname{lcm}(6, 15)$.

   Solution

   $\gcd$ and $\operatorname{lcm}$

   • $\gcd(18,30)$
     • Prime factorizations:
       • $18 = 2 \cdot 3^2$
       • $30 = 2 \cdot 3 \cdot 5$
     • Common prime factors with smallest exponents: $2^1 \cdot 3^1 = 6$
     • So: $$\gcd(18,30) = 6$$
   • $\operatorname{lcm}(6,15)$
     • Prime factorizations:
       • $6 = 2 \cdot 3$
       • $15 = 3 \cdot 5$
     • Take all primes with largest exponents: $2^1 \cdot 3^1 \cdot 5^1 = 30$
     • So: $$\operatorname{lcm}(6,15) = 30$$